【UVA12657】 Boxes in a Line

发表于

改了一百年终于过了

此题用链表可以更快一点

链表细节是真的多~~

先说明一下next是指向此数后面的类指针，prev是指向前面的类指针。（双向链表对吧）

主要函数1：

1
2
3
4
void link(int x,int y) {
    a[x].next=y;
    a[y].prev=x;
}

用于将链表中的两点连起来

主要函数2：

我们用第一种，将x插入到y后面举例：

  1. 先把x的左右两边连起来（把x从原先位置拿出来）
  2. 再让y.prev（y的上一个数）和x连起来
  3. 最后把x和y连起来

注意：第2步和第3步不能交换（请读者思考）

以下为此函数代码：

1
2
3
4
5
void op1(int x,int y) {
    link(a[x].prev,a[x].next);
    link(a[y].prev,x);
    link(x,y);
}

后面两种情况思路大致相同

最后来说说操作4

这就是此题精髓之处

为了让我们的程序运行速度更快，我们不必每次遇到操作4都反转一次链表。想一想，反转一次后再翻转过来其实就是没反转，然而问题来了，操作1和2在这期间不会混乱吗？所以我们记录操作4操作操作的此数，在偶数次时正常操作，在奇数次时就反过来操作，即若是操作1就换成操作2，操作2的话就操作1。这样可以大大节省时间。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<cstdio>
using namespace std;
int ans2,n,m;
struct node {
    int prev,next;
} a[100005];
void link(int x,int y) {
    a[x].next=y;
    a[y].prev=x;
}
void op1(int x,int y) {
    link(a[x].prev,a[x].next);
    link(a[y].prev,x);
    link(x,y);
}
void op2(int x,int y) {
    link(a[x].prev,a[x].next);
    link(x,a[y].next);
    link(y,x);
}
void op3(int x,int y) {
    //这里要注意特判，若是两者本连在一起
    //就会出现问题，因为x.next就是y或x.prev是y
    //所以分情况写，要不然会导致TLE
    int leftx=a[x].prev;
    int rightx=a[x].next;
    int lefty=a[y].prev;
    int righty=a[y].next;
    if(a[x].next==y){//情况1
        link(x,righty);
        link(leftx,y);
        link(y,x);
        return ;
    }
    if(a[x].prev==y){//请况2
        link(y,rightx);
        link(lefty,x);
        link(x,y);
        return ;
    }
    link(leftx,y);//一般情况
    link(y,rightx);
    link(lefty,x);
    link(x,righty);
}
int main() {
    while(cin>>n>>m) {//没有数据后停止
        int op,xx,yy;
        long long ans=0;
        ans2++;
        bool ok=0,ok2=0;
        link(0,1);
        link(1,n+1);
        for(int i=2; i<=n; i++) {//将数插入链表
            link(i,a[i-1].next);
            link(i-1,i);
        }
        for(int i=1; i<=m; i++) {
            cin>>op
            if(op==4) ok=!ok;//标记操作4出现奇偶次数
            else cin>>xx>>yy;
            if(ok==0){//偶数次
                if(op==1)op1(xx,yy);
                if(op==2)op2(xx,yy);
                if(op==3)op3(xx,yy);
            }
            else {//奇数次
                if(op==1)op2(xx,yy);
                if(op==2)op1(xx,yy);
                if(op==3)op3(xx,yy);
            }
        }
        //还有操作4奇偶次数会导致最后链表中奇数位置编号
        //不一样，所以还是要分开。
        if(ok==0){
            for(int i=a[0].next;i!=n+1;i=a[i].next){
                //cout<<i<<" ";
                if(ok2==1) ok2=0;
                else {
                    ok2=1;ans+=i;
                }
            }
        }
        else {
            for(int i=a[0].next;i!=n+1;i=a[i].next){
                if(ok2==0) ok2=1;
                else {
                    ok2=0;
                    ans+=i;//cout<<i<<" ";
                }
            }
        }
        //for(int i=a[0].next;i!=n+1;i=a[i].next)cout<<i<<" ";
        printf("Case %d: %lld\n",ans2,ans);
        //输出注意Case后面有空格，“：”后面也有空格（坑~~）
    }
}